/*
* Authors: Karymov Anton
*          Skorodumov Kirill
* This file contains headers for branching algorythm.
* June-August,	2011
*/


#pragma once

#include "types.h"

class branching_algorythm {
private:
  graph_t g;
  unsigned int optimization_level;
  unsigned int covered_edges_count;
  //vector for marking processed vertices
  std::vector<bool> processed_vertices;
  unsigned int cover_size;

  //property maps
  boost::property_map<graph_t, boost::vertex_included_t>::type included_map;
  boost::property_map<graph_t, boost::edge_covered_t>::type covered_map;
  boost::property_map<graph_t, boost::vertex_name_t>::type name_map;

  // main searching function
  bool branch(vertex_t v, int k);
  void include_vertex(vertex_t v);
  void exclude_vertex(vertex_t v);

  //optimization
  void optimization_degree_one(int & k);

  //getters and setters for property maps
  void set_cover(edge_t e, bool value);
  bool get_cover(edge_t e) const;
  void set_include(vertex_t v, bool value);
  bool get_include(vertex_t v) const;

  int uncovered_neighbours(vertex_t v); 
  bool graph_already_covered() const;
  void fill_name_map();
  bool internal_solve(int k);


public:
  branching_algorythm(graph_t & g_);	
  bool solve(const int k);	
  int number_of_vertices() const;
  unsigned int get_cover_size() const;
  void set_optimization_level(unsigned int level);
  boost::property_map<graph_t, boost::vertex_name_t>::type get_name_map();
};